package wwl.lsf;

import wwl.lsf.base.ListNode;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

/**
 * @Title
 * @Author wangwenliang
 * @Date 2021/5/24
 * @Description
 */
public class 合并K个排序链表 {

    class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            PriorityQueue<ListNode> q = new PriorityQueue<>((x, y) -> x.val - y.val);
            for (ListNode node : lists) {
                if (node != null) {
                    q.add(node);
                }
            }
            ListNode head = new ListNode(0);
            ListNode tail = head;
            while (!q.isEmpty()) {
                tail.next = q.poll();
                tail = tail.next;
                if (tail.next != null) {
                    q.add(tail.next);
                }
            }
            return head.next;
        }
    }

    public static ListNode youxianjiduilie(ListNode[] lists) {

        PriorityQueue<ListNode> priorityQueue = new PriorityQueue<>((x, y) -> x.val - y.val);

        for (ListNode listNode : lists) {
            priorityQueue.add(listNode);
        }

        ListNode pre = new ListNode(0);

        ListNode tail = pre;

        while (!priorityQueue.isEmpty()) {
            ListNode poll = priorityQueue.poll();
            tail.next = poll;
            tail = poll;
            if (poll.next != null) {
                priorityQueue.add(poll.next);
            }
        }
        return pre.next;
    }

    public static void main(String[] args) {

        ListNode listNode5 = new ListNode(5);
        ListNode listNode3 = new ListNode(3, listNode5);
        ListNode listNode1 = new ListNode(1, listNode3);


        ListNode listNode6 = new ListNode(6);
        ListNode listNode4 = new ListNode(4, listNode6);
        ListNode listNode2 = new ListNode(2, listNode4);

        ListNode[] listNodes = {listNode1, listNode2};
        ListNode youxianjiduilie = youxianjiduilie(listNodes);

        while (youxianjiduilie != null) {
            System.out.println("youxianjiduilie = " + youxianjiduilie.val);
            youxianjiduilie = youxianjiduilie.next;
        }
    }
}
